package class04

import "math"


/*
	给定一个数组arr，返回子数组的最大累加和

	流程：
		两个变量，cur初始为0，max 为系统最小
		当cur到一个位置时，累加当前位置的值，与 max 取最大值
		当前cur如过小于0，重新设置为0为下一次搜集答案做准备

	原理验证的方式可以使用 答案假设法
	先假设 i-j 之间时答案，考虑区间之前与区间重点不能称为答案的限制，带入流程，如果满足，即可。
*/
func maxSum(arr []int) int {
	var cur int
	ans := math.MinInt
	for i:=0; i<len(arr); i++ {
		cur += arr[i]
		ans = max(ans, arr[i])
		if cur < 0 {
			cur = 0
		}
	}
	return ans
}
